package example.exam;

import java.util.HashSet;

/**
 * 一个n X m的只由小写英文字母组成的矩阵 ，
 * 牛牛想找到一个面积最小的正方形子矩阵满足该正方形子矩阵包含至少种不同的字母。
 */
public class Main {

    /**
     * @param chars
     * @param m
     * @param n
     * @param count
     * @return
     */
    public int findMatch1(char[][] chars, int m, int n, int count) {
        int result = 0;
        int x = chars.length;
        int y = chars[0].length;
        if (m > x || n > y || count > (x * y)) {
            return -1;
        }
        int abs = Math.abs(count);
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                int xstart = i, ystart = j;
                int xend = i + m - 1, yend = j + n - 1;
                if (xend >= x || yend >= y) {
                    continue;
                }
                int size = 0;
                HashSet<Character> set = new HashSet<>(count);
                for (int k = xstart; k <= xend; k++) {
                    for (int l = ystart; l <= yend; l++) {
                        if (set.add(chars[k][l])) {
                            size++;
                        }
                    }
                }
                if (size == count) {
                    result++;
                }
            }
        }
        return -1;
    }

    /**
     * @param chars chars二维数组
     * @param m     char 长
     * @param n     char 宽
     * @param count 最小正方体的个数
     * @return
     */
    public int findMatch(char[][] chars, int m, int n, int count) {
        if (count > (m * n)) {
            return -1;
        }
        int result = 0;
        //先获取到最小的宽度   先求平方+再向上取整
        //如果最小宽度不符合，宽度+1
        int xxx = (int) Math.ceil(Math.sqrt(count));
        while (result == 0 && xxx < m && xxx < n) {
            result = getResult(chars, count, m, n, xxx);
            xxx++;
        }
        return result == 0 ? -1 : result;
    }

    private int getResult(char[][] chars, int count, int x, int y, int xxx) {
        int result = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                int xstart = i, ystart = j;
                int xend = i + xxx - 1, yend = j + xxx - 1;
                if (xend >= x || yend >= y) {
                    continue;
                }
                int size = 0;
                HashSet<Character> set = new HashSet<>(count);
                for (int k = xstart; k <= xend; k++) {
                    for (int l = ystart; l <= yend; l++) {
                        if (set.add(chars[k][l])) {
                            size++;
                        }
                    }
                }
                if (size == count) {
                    result++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Main main = new Main();
        char[][] chars = new char[][]{
                {'a', 'a', 'b', 'c'},
                {'a', 'a', 'a', 'a'},
                {'a', 'x', 'a', 'z'},
                {'a', 'b', 'c', 'd'}};
        System.out.println(main.findMatch(chars, 4, 4, 9));
    }
}
